import com.sun.jmx.snmp.SnmpUnknownMsgProcModelException;

import java.util.Arrays;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] arr=new int[2];
        int i=0;
        int j=numbers.length-1;
        while(i<j){
            int tmp=numbers[i]+numbers[j];
            if(tmp>target){
                j--;
            }else if(tmp<target){
                i++;
            }else{
                arr[0]=i;
                arr[1]=j;
                break;
            }
        }
        return arr;
    }





    public String addBinary(String a, String b) {
        return Integer.toBinaryString(
                Integer.parseInt(a, 2) + Integer.parseInt(b, 2)
        );
    }




    public boolean isStraight(int[] nums) {
        int joker=0;
        Arrays.sort(nums);
        for(int i=0;i<4;i++){
            if(nums[i]==0){
                joker++;
            }else if(nums[i]==nums[i+1]){
                return false;
            }
        }
        return nums[4]-nums[joker]<5;
    }



    public String reverseWords(String s) {
        String[] str=s.trim().split(" ");
        StringBuilder sb=new StringBuilder();
        for(int i=str.length-1;i>=0;i--){
            if(str[i].equals("")){
                continue;
            }
            sb.append(str[i]+" ");
        }
        return sb.toString().trim();
    }





    public int missingNumber(int[] nums) {
        int sum=0;
        int ans=0;
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
            ans+=nums.length-i;
        }
        return ans-sum;
    }





    public int search(int[] nums, int target) {
        int count=0;
        for(int tmp : nums){
            if(tmp==target){
                count++;
            }
        }
        return count;
    }






    public int maxSubArray(int[] nums) {
        int tmp=0;
        int max=nums[0];
        for(int ans : nums){
            tmp=Math.max(tmp+ans,ans);
            max=Math.max(tmp,max);
        }
        return max;
    }



    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        int mid=nums.length/2;
        return nums[mid];
    }






    public int[] exchange(int[] nums) {
        if(nums.length==0){
            return nums;
        }
        int i=0;
        int j=nums.length-1;
        while(i<j){
            while(nums[i]%2!=0&&i<j){
                i++;
            }
            while(nums[j]%2!=1&&i<j){
                j--;
            }
            int tmp=nums[i];
            nums[i]=nums[j];
            nums[j]=tmp;
        }
        return nums;
    }








    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int row=matrix.length;
        if(row==0){
            return false;
        }
        int col=matrix[0].length;
        if(col==0){
            return false;
        }
        int i=0;
        int j=col-1;
        while(i<row&&j>=0){
            if(matrix[i][j]>target){
                j--;
            }else if(matrix[i][j]<target){
                i++;
            }else{
                return true;
            }
        }
        return false;
    }





    public int findRepeatNumber(int[] nums) {
        Arrays.sort(nums);
        for(int i=0;i<nums.length-1;i++){
            if(nums[i]==nums[i+1]){
                return nums[i];
            }
        }
        return -1;
    }






    public int countSegments(String s) {
        int count=0;
        String[] str=s.split(" ");
        for(String ch : str){
            if(!ch.equals(" ")){
                count++;
            }
        }
        return count;
    }
}





